package com.xjl.everyinterview.datastructureandalgorithm.datastructure.link;

/**
 * @author xjl
 * @version .0
 * @description: TODO
 * @date 0/8/3 8:00
 */
public class MyLinkImpl implements MyLink {

    //头节点指针
    private Node head;
    // 尾节点指针
    private Node last;
    //链表实际长度
    private int size;

    @Override
    public void insert(int data, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(" 超出链表节点范围！");
        }
        Node insertedNode = new Node(data);

        if (size == 0) {  //空链表
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {  //插入头部

            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            //插入中间
            Node prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;

    }

    /**
     * @description: 根据位置删除某个节点
     * 思路
     * 删除第一个
     * 1头节点赋值给临时变量
     * 2 头节点等于临时变量的next
     * 删除最后一个
     * 1 获取删除节点的上一个节点
     * 2上个节点等于最后一个节点
     * 3 置空最后一个节点
     * 删除中间的
     * 1 保存上个节点到临时变量
     * 2 保存下个节点到临时变量
     * 3 上个个节点指向next next 节点  完成
     * @author xjl
     * @date: 2021/8/14 10:28
     * @param: index  节点位置
     * @return:
     **/
    @Override
    public Node delete(int index) {
        Node removedNode = null;
        if (index < 0 && index >= size) {
            throw new IndexOutOfBoundsException(" 超出链表节点范围！");
        }
//      删除分为几种情况
//      1 删除头节点
//      2 删除尾节点
//      3删除中间节点
//      获取要删除的上个节点

        if (index == 0) {
            Node temp = head;
            removedNode = head;
            temp.next = head;
        } else if (index == size) {
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        } else {
            //获取到上个节点
            Node prevNode = get(index-1);
            //获取到要删除的节点
            removedNode = prevNode.next;

            prevNode.next = prevNode.next.next;
        }
        size--;
        return removedNode;
    }

    @Override
    public void update(int data, int index) {
        if (index < 0 && index >= size) {
            throw new IndexOutOfBoundsException(" 超出链表节点范围！");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        //获取到某个位置并且替换值
        temp.setData(data);
    }

    @Override
    public Node get(int index) {
        //判断传过来的值要大于0  并且  传过来的值要小于或等于链表的大小
        if (index < 0 && index >= size) {
            throw new IndexOutOfBoundsException(" 超出链表节点范围！");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }

        return temp;
    }

    @Override
    public void outPut() {
        Node tamp = head;
        while (tamp != null) {
            System.out.println(tamp.getData());
            tamp = tamp.next;
        }
    }
}
